#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<mpi.h>

# define qtdePalavras 65200
# define MAXPALAVRA 6
# define ALFABETO 26
# define MAXLOOP 1000

// variaveis globais
char dicionario[qtdePalavras][MAXPALAVRA];

unsigned ind_max = 0;

int gera_aleatorio(char *word, int rank, int *vet_encontradas){
	int i = 0, indice= -1;
	
	for(i=0;i<MAXPALAVRA; i++){
		word[i] = (rand()%ALFABETO) + 97; 
		word[i+1] = '\0';
		
		indice = busca_palavra(word);
		
		if(indice >= 0){
			if(vet_encontradas[indice] == 0){
				//printf("Rank: %d encontrou: %s, indice: %d no dicionario\n", rank, word, indice);
				return indice;
			}
		}
	}
	
	return -1; //nao achou 

}
int busca_palavra(char *palavra){
	int i = 0;
	for(i=0;i<ind_max; i++){
		if(strcmp(dicionario[i], palavra) == 0)
			return i;
	}
	return -1;
}
float calcula_porcentagem(int *vetor_encontrada){
	int i=0, soma=0;
	for(i=0;i<ind_max;i++){
		soma=soma+vetor_encontrada[i];
	}

	return (float)soma/(float)(ind_max);
}
// funcao principal
int main (int argc, char *argv[]) {
	
	FILE * arqIn;
	
	char word[20];
	unsigned i=0, j=0, k=0;
	
    clock_t inicio, fim;
    double tempo;
    
	// variaveis usadas para MPI
    int numprocs, rank, namelen, rc;
    char processor_name[MPI_MAX_PROCESSOR_NAME];
   	
    
	// abertura do arquivo com palavras do dicionario
	if(!(arqIn = fopen("Max5.txt", "r"))){
		printf("Erro ao abrir o arquivo!\n\n");
		return -1;
	}
	
	for(i=0; !feof(arqIn) ;i++){ //carregando o dicionario para a memoria
		fscanf(arqIn, "%s\n", dicionario[i]);
	}
	ind_max=i;
	
	fclose(arqIn);
	MPI_Status Stat;
    rc = MPI_Init(&argc, &argv);

    if(rc != MPI_SUCCESS){
            printf("Falha ao iniciar MPI\n\n");
            exit(-1);
    }
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Get_processor_name(processor_name, &namelen);
    
    int encontrada[numprocs][qtdePalavras];
    srand(time(NULL) + rank);

	for(j=0;j<numprocs;j++){
		for(i=0;i<ind_max;i++){
			encontrada[j][i] = 0;
		}
		for(i=ind_max;i<qtdePalavras;i++){
			encontrada[j][i] = -1;
		}
	}
 
    if(rank == 0){ // mestre
		int nao_terminou=1;
		float porcentagem_encontrada = 0.0, porcentagem_anterior = 0.0, diferenca = 0.0;
		inicio = clock(); //loop de calculo
				printf("-------------------------------------------------------------\n");
				printf("Starting clock at time = 0.00\n");
		while(nao_terminou){
			
		
			for(k=1;k<numprocs;k++){
				MPI_Recv(encontrada[k], ind_max, MPI_INT, k, 1, MPI_COMM_WORLD, &Stat);
			}
			/*
			* Calcula % de palavras encontradas
			* printa a cada 10%
			* termina se encontrou 100% :)
			*/	
			
			for(k=1;k<numprocs;k++){ // indice dos filhos
				for(j=0;j<ind_max;j++){ //percorre o vetor de palavras encontradas de cada filho
					if(encontrada[k][j] == 1){
						encontrada[0][j] = 1;
					}
				}
			}    
		
			porcentagem_anterior = porcentagem_encontrada;
			porcentagem_encontrada = calcula_porcentagem(encontrada[0]);
			diferenca = diferenca + (porcentagem_encontrada - porcentagem_anterior);
			if((porcentagem_encontrada == 1.00) || (porcentagem_encontrada >= 0.9999)){
				printf("-------------------------------------------------------------\n");
				printf("Finished %.2f percent in", porcentagem_encontrada*100);
				nao_terminou = 0;
			}
			else if (diferenca >= 0.10){
				fim = clock();
				tempo = ((fim-inicio)/(CLOCKS_PER_SEC/1000));
				printf("Found just  %.2f percent in clock time = %.2f\n", porcentagem_encontrada*100, tempo);
				diferenca = 0.0;
			}			
	
			for(k=1;k<numprocs;k++)
				MPI_Send(&porcentagem_encontrada, 1, MPI_FLOAT, k, 1, MPI_COMM_WORLD);
			
		}	
		fim = clock();
		tempo = ((fim-inicio)/(CLOCKS_PER_SEC/1000));
		printf(" %.2f miliseconds\n", tempo);    	
		printf("-------------------------------------------------------------\n");	
    }		
	else{ // escravos
		int continua = 1, multifactor = 1;
		float porcentagem_encontrada = 0.0, porcentagem_anterior = 0.0, diferenca = 0.0;
		
		while(1){
			while(continua < (MAXLOOP * multifactor)){
				int indice = gera_aleatorio(word, rank, encontrada[rank]);
				/*
				Se encontrou palavra, marca no vetor encontrada
				*/
				//int indice = busca_palavra("aback");
			
				if(indice >= 0){
					encontrada[rank][indice] = 1;
					//printf("Rank: %d encontrou: %s, indice: %d\n", rank, word, indice);
				}
				
				continua++;
			}
			MPI_Send(encontrada[rank], ind_max, MPI_INT, 0, 1, MPI_COMM_WORLD);
			porcentagem_anterior = porcentagem_encontrada;
			diferenca = diferenca + (porcentagem_encontrada - porcentagem_anterior);
			MPI_Recv(&porcentagem_encontrada, 1, MPI_FLOAT, 0, 1, MPI_COMM_WORLD, &Stat);
			if((porcentagem_encontrada >= 0.9999) || (porcentagem_encontrada == 1.000)) 
				break;
			else if(diferenca >= 0.10){
				multifactor *= 10;
				diferenca = 0.0;
			}
			continua = 1;
		}
	}

	MPI_Barrier(MPI_COMM_WORLD);
	MPI_Finalize();		

	return 0;
}
